home *** CD-ROM | disk | FTP | other *** search
/ FishMarket 1.0 / FishMarket v1.0.iso / fishies / 101-125 / disk_105 / bison / conflicts.c < prev    next >
C/C++ Source or Header  |  1992-05-06  |  14KB  |  690 lines
  1. /* Find and resolve or report look-ahead conflicts for bison,
  2.    copyright (C) 1984 Bob Corbett and Richard Stallman
  3.  
  4.    Permission is granted to anyone to make or distribute verbatim copies of this program
  5.    provided that the copyright notice and this permission notice are preserved;
  6.    and provided that the recipient is not asked to waive or limit his right to
  7.    redistribute copies as permitted by this permission notice;
  8.    and provided that anyone possessing an executable copy
  9.    is granted access to copy the source code, in machine-readable form,
  10.    in some reasonable manner.
  11.  
  12.    Permission is granted to distribute derived works or enhanced versions of
  13.    this program under the above conditions with the additional condition
  14.    that the entire derivative or enhanced work
  15.    must be covered by a permission notice identical to this one.
  16.  
  17.    Anything distributed as part of a package containing portions derived
  18.    from this program, which cannot in current practice perform its function usefully
  19.    in the absense of what was derived directly from this program,
  20.    is to be considered as forming, together with the latter,
  21.    a single work derived from this program,
  22.    which must be entirely covered by a permission notice identical to this one
  23.    in order for distribution of the package to be permitted.
  24.  
  25.  In other words, you are welcome to use, share and improve this program.
  26.  You are forbidden to forbid anyone else to use, share and improve
  27.  what you give them.   Help stamp out software-hoarding!  */
  28.  
  29. #include <stdio.h>
  30. #include "machine.h"
  31. #include "new.h"
  32. #include "files.h"
  33. #include "gram.h"
  34. #include "state.h"
  35.  
  36.  
  37. extern char **tags;
  38. extern int tokensetsize;
  39. extern char *consistent;
  40. extern short *accessing_symbol;
  41. extern shifts **shift_table;
  42. extern unsigned *LA;
  43. extern short *LAruleno;
  44. extern short *lookaheads;
  45. extern int verboseflag;
  46.  
  47. char any_conflicts;
  48. char *conflicts;
  49.  
  50.  
  51. static unsigned *shiftset;
  52. static unsigned *lookaheadset;
  53. static int src_total;
  54. static int rrc_total;
  55. static int src_count;
  56. static int rrc_count;
  57.  
  58.  
  59.  
  60. initialize_conflicts()
  61. {
  62.   register int i;
  63.  
  64.   conflicts = NEW2(nstates, char);
  65.   shiftset = NEW2(tokensetsize, unsigned);
  66.   lookaheadset = NEW2(tokensetsize, unsigned);
  67.  
  68.   any_conflicts = 0;
  69.  
  70.   for (i = 0; i < nstates; i++)
  71.     set_conflicts(i);
  72. }
  73.  
  74.  
  75.  
  76. set_conflicts(state)
  77. int state;
  78. {
  79.   register int i;
  80.   register int k;
  81.   register shifts *shiftp;
  82.   register unsigned *fp2;
  83.   register unsigned *fp3;
  84.   register unsigned *fp4;
  85.   unsigned *fp1;
  86.   register int symbol;
  87.  
  88.   if (consistent[state]) return;
  89.  
  90.   for (i = 0; i < tokensetsize; i++)
  91.     lookaheadset[i] = 0;
  92.  
  93.   shiftp = shift_table[state];
  94.   if (shiftp)
  95.     {
  96.       k = shiftp->nshifts;
  97.       for (i = 0; i < k; i++)
  98.     {
  99.       symbol = accessing_symbol[shiftp->shifts[i]];
  100.       if (ISVAR(symbol)) break;
  101.       SETBIT(lookaheadset, symbol);
  102.     }
  103.     }
  104.  
  105.   k = lookaheads[state + 1];
  106.   fp4 = lookaheadset + tokensetsize;
  107.  
  108.   /* loop over all rules which require lookahead in this state */
  109.   /* first check for shift-reduce conflict, and try to resolve using precedence  */
  110.  
  111.   for (i = lookaheads[state]; i < k; i++)
  112.     if (rprec[LAruleno[i]])
  113.       {
  114.     fp1 = LA + i * tokensetsize;
  115.     fp2 = fp1;
  116.     fp3 = lookaheadset;
  117.   
  118.     while (fp3 < fp4)
  119.       {
  120.         if (*fp2++ & *fp3++)
  121.           {
  122.         resolve_sr_conflict(state, i);
  123.         break;
  124.           }
  125.       }
  126.       }
  127.  
  128.   /* loop over all rules which require lookahead in this state */
  129.   /* Check for conflicts not resolved above.  */
  130.  
  131.   for (i = lookaheads[state]; i < k; i++)
  132.     {
  133.       fp1 = LA + i * tokensetsize;
  134.       fp2 = fp1;
  135.       fp3 = lookaheadset;
  136.  
  137.       while (fp3 < fp4)
  138.     {
  139.       if (*fp2++ & *fp3++)
  140.         {
  141.           conflicts[state] = 1;
  142.           any_conflicts = 1;
  143.         }
  144.     }
  145.  
  146.       fp2 = fp1;
  147.       fp3 = lookaheadset;
  148.  
  149.       while (fp3 < fp4)
  150.     *fp3++ |= *fp2++;
  151.     }
  152. }
  153.  
  154.  
  155.  
  156. /* Attempt to resolve shift-reduce conflict for one rule
  157. by means of precedence declarations.
  158. It has already been checked that the rule has a precedence.
  159. A conflict is resolved by modifying the shift or reduce tables
  160. so that there is no longer a conflict.  */
  161.  
  162. resolve_sr_conflict(state, lookaheadnum)
  163. int state;
  164. int lookaheadnum;
  165. {
  166.   register int i;
  167.   register int mask;
  168.   register unsigned *fp1;
  169.   register unsigned *fp2;
  170.   register int redprec;
  171.  
  172.   /* find the rule to reduce by to get precedence of reduction  */
  173.   redprec = rprec[LAruleno[lookaheadnum]];
  174.  
  175.   mask = 1;
  176.   fp1 = LA + lookaheadnum*tokensetsize;
  177.   fp2 = lookaheadset;
  178.   for (i = 0; i < ntokens; i++)
  179.     {
  180.       if ((mask & *fp2 & *fp1) && sprec[i])
  181.     /* shift-reduce conflict occurs for token number i and it has a precision.
  182.        The precedence of shifting is that of token i.  */
  183.     {
  184.       if (sprec[i] < redprec)
  185.         {
  186.           if (verboseflag) log_resolution(state, lookaheadnum, i, "reduce");
  187.           *fp2 &= ~mask;  /* flush the shift for this token */
  188.           flush_shift(state, i);
  189.         }
  190.       else if (sprec[i] > redprec)
  191.         {
  192.           if (verboseflag) log_resolution(state, lookaheadnum, i, "shift");
  193.           *fp1 &= ~mask;  /* flush the reduce for this token */
  194.         }
  195.       else
  196.         {
  197.           /* Matching precedence levels.
  198.          For left association, keep only the reduction.
  199.          For right association, keep only the shift.
  200.          For nonassociation, keep neither.  */
  201.  
  202.           switch (sassoc[i])
  203.         {
  204.  
  205.         case RIGHT_ASSOC:
  206.               if (verboseflag) log_resolution(state, lookaheadnum, i, "shift");
  207.           break;
  208.  
  209.         case LEFT_ASSOC:
  210.               if (verboseflag) log_resolution(state, lookaheadnum, i, "reduce");
  211.           break;
  212.  
  213.         case NON_ASSOC:
  214.               if (verboseflag) log_resolution(state, lookaheadnum, i, "an error");
  215.           break;
  216.         }
  217.  
  218.           if (sassoc[i] != RIGHT_ASSOC)
  219.         {
  220.           *fp2 &= ~mask;  /* flush the shift for this token */
  221.           flush_shift(state, i);
  222.         }
  223.           if (sassoc[i] != LEFT_ASSOC)
  224.             {
  225.           if (verboseflag) log_resolution(state, lookaheadnum, i, "shift");
  226.           *fp1 &= ~mask;  /* flush the reduce for this token */
  227.         }
  228.         }
  229.     }
  230.  
  231.       mask <<= 1;
  232.       if (mask == 0)
  233.     {
  234.       mask = 1;
  235.       fp2++;  fp1++;
  236.     }
  237.     }
  238. }
  239.  
  240.  
  241.  
  242. /* turn off the shift recorded for the specified token in the specified state.
  243. Used when we resolve a shift-reduce conflict in favor of the reduction.  */
  244.  
  245. flush_shift(state, token)
  246. int state;
  247. int token;
  248. {
  249.   register shifts *shiftp;
  250.   register int k, i;
  251.  
  252.   shiftp = shift_table[state];
  253.  
  254.   if (shiftp)
  255.     {
  256.       k = shiftp->nshifts;
  257.       for (i = 0; i < k; i++)
  258.     {
  259.       if (shiftp->shifts[i] && token == accessing_symbol[shiftp->shifts[i]])
  260.         (shiftp->shifts[i]) = 0;
  261.     }
  262.     }
  263. }
  264.  
  265.  
  266.  
  267. log_resolution(state, LAno, token, resolution)
  268. int state, LAno, token;
  269. char *resolution;
  270. {
  271.   fprintf(foutput,
  272.       "Conflict in state %d between rule %d and token %s resolved as %s.\n",
  273.       state, LAruleno[LAno], tags[token], resolution);
  274. }
  275.  
  276.  
  277.  
  278. conflict_log()
  279. {
  280.   register int i;
  281.  
  282.   src_total = 0;
  283.   rrc_total = 0;
  284.  
  285.   for (i = 0; i < nstates; i++)
  286.     {
  287.       if (conflicts[i])
  288.     {
  289.       count_sr_conflicts(i);
  290.       count_rr_conflicts(i);
  291.       src_total += src_count;
  292.       rrc_total += rrc_count;
  293.     }
  294.     }
  295.  
  296.   total_conflicts();
  297. }
  298.   
  299.  
  300.  
  301. verbose_conflict_log()
  302. {
  303.   register int i;
  304.  
  305.   src_total = 0;
  306.   rrc_total = 0;
  307.  
  308.   for (i = 0; i < nstates; i++)
  309.     {
  310.       if (conflicts[i])
  311.     {
  312.       count_sr_conflicts(i);
  313.       count_rr_conflicts(i);
  314.       src_total += src_count;
  315.       rrc_total += rrc_count;
  316.  
  317.       fprintf(foutput, "State %d contains", i);
  318.  
  319.       if (src_count == 1)
  320.         fprintf(foutput, " 1 shift/reduce conflict");
  321.       else if (src_count > 1)
  322.         fprintf(foutput, " %d shift/reduce conflicts", src_count);
  323.  
  324.       if (src_count > 0 && rrc_count > 0)
  325.         fprintf(foutput, " and");
  326.  
  327.       if (rrc_count == 1)
  328.         fprintf(foutput, " 1 reduce/reduce conflict");
  329.       else if (rrc_count > 1)
  330.         fprintf(foutput, " %d reduce/reduce conflicts", rrc_count);
  331.  
  332.       putc('.', foutput);
  333.       putc('\n', foutput);
  334.     }
  335.     }
  336.  
  337.   total_conflicts();
  338. }
  339.  
  340.  
  341.  
  342. total_conflicts()
  343. {
  344.   fprintf(stderr, "%s contains", infile);
  345.  
  346.   if (src_total == 1)
  347.     fprintf(stderr, " 1 shift/reduce conflict");
  348.   else if (src_total > 1)
  349.     fprintf(stderr, " %d shift/reduce conflicts", src_total);
  350.  
  351.   if (src_total > 0 && rrc_total > 0)
  352.     fprintf(stderr, " and");
  353.  
  354.   if (rrc_total == 1)
  355.     fprintf(stderr, " 1 reduce/reduce conflict");
  356.   else if (rrc_total > 1)
  357.     fprintf(stderr, " %d reduce/reduce conflicts", rrc_total);
  358.  
  359.   putc('.', stderr);
  360.   putc('\n', stderr);
  361. }
  362.  
  363.  
  364.  
  365. count_sr_conflicts(state)
  366. int state;
  367. {
  368.   register int i;
  369.   register int k;
  370.   register int mask;
  371.   register shifts *shiftp;
  372.   register unsigned *fp1;
  373.   register unsigned *fp2;
  374.   register unsigned *fp3;
  375.   register int symbol;
  376.  
  377.   src_count = 0;
  378.  
  379.   shiftp = shift_table[state];
  380.   if (!shiftp) return;
  381.  
  382.   for (i = 0; i < tokensetsize; i++)
  383.     {
  384.       shiftset[i] = 0;
  385.       lookaheadset[i] = 0;
  386.     }
  387.  
  388.   k = shiftp->nshifts;
  389.   for (i = 0; i < k; i++)
  390.     {
  391.       if (! shiftp->shifts[i]) continue;
  392.       symbol = accessing_symbol[shiftp->shifts[i]];
  393.       if (ISVAR(symbol)) break;
  394.       SETBIT(shiftset, symbol);
  395.     }
  396.  
  397.   k = lookaheads[state + 1];
  398.   fp3 = lookaheadset + tokensetsize;
  399.  
  400.   for (i = lookaheads[state]; i < k; i++)
  401.     {
  402.       fp1 = LA + i * tokensetsize;
  403.       fp2 = lookaheadset;
  404.  
  405.       while (fp2 < fp3)
  406.     *fp2++ |= *fp1++;
  407.     }
  408.  
  409.   fp1 = shiftset;
  410.   fp2 = lookaheadset;
  411.  
  412.   while (fp2 < fp3)
  413.     *fp2++ &= *fp1++;
  414.  
  415.   mask = 1;
  416.   fp2 = lookaheadset;
  417.   for (i = 0; i < ntokens; i++)
  418.     {
  419.       if (mask & *fp2)
  420.     src_count++;
  421.  
  422.       mask <<= 1;
  423.       if (mask == 0)
  424.     {
  425.       mask = 1;
  426.       fp2++;
  427.     }
  428.     }
  429. }
  430.  
  431.  
  432.  
  433. count_rr_conflicts(state)
  434. int state;
  435. {
  436.   register int i;
  437.   register int j;
  438.   register int count;
  439.   register unsigned mask;
  440.   register unsigned *baseword;
  441.   register unsigned *wordp;
  442.   register int m;
  443.   register int n;
  444.  
  445.   rrc_count = 0;
  446.  
  447.   m = lookaheads[state];
  448.   n = lookaheads[state + 1];
  449.  
  450.   if (n - m < 2) return;
  451.  
  452.   mask = 1;
  453.   baseword = LA + m * tokensetsize;
  454.   for (i = 0; i < ntokens; i++)
  455.     {
  456.       wordp = baseword;
  457.  
  458.       count = 0;
  459.       for (j = m; j < n; j++)
  460.     {
  461.       if (mask & *wordp)
  462.         count++;
  463.  
  464.       wordp += tokensetsize;
  465.     }
  466.  
  467.       if (count >= 2) rrc_count++;
  468.  
  469.       mask <<= 1;
  470.       if (mask == 0)
  471.     {
  472.       mask = 1;
  473.       baseword++;
  474.     }
  475.     }
  476. }
  477.  
  478.  
  479.  
  480. print_reductions(state)
  481. int state;
  482. {
  483.   register int i;
  484.   register int j;
  485.   register int k;
  486.   register unsigned *fp1;
  487.   register unsigned *fp2;
  488.   register unsigned *fp3;
  489.   register unsigned *fp4;
  490.   register int rule;
  491.   register int symbol;
  492.   register unsigned mask;
  493.   int m;
  494.   int n;
  495.   int default_LA;
  496.   int default_rule;
  497.   int cmax;
  498.   int count;
  499.   shifts *shiftp;
  500.   int nodefault = 0;
  501.  
  502.   for (i = 0; i < tokensetsize; i++)
  503.     shiftset[i] = 0;
  504.  
  505.   shiftp = shift_table[state];
  506.   if (shiftp)
  507.     {
  508.       k = shiftp->nshifts;
  509.       for (i = 0; i < k; i++)
  510.     {
  511.       if (! shiftp->shifts[i]) continue;
  512.       symbol = accessing_symbol[shiftp->shifts[i]];
  513.       if (ISVAR(symbol)) break;
  514.       /* if this state has a shift for the error token,
  515.          don't use a default rule.  */
  516.       if (symbol == error_token_number) nodefault = 1;
  517.       SETBIT(shiftset, symbol);
  518.     }
  519.     }
  520.  
  521.   m = lookaheads[state];
  522.   n = lookaheads[state + 1];
  523.  
  524.   if (n - m == 1 && ! nodefault)
  525.     {
  526.       default_rule = LAruleno[m];
  527.  
  528.       fp1 = LA + m * tokensetsize;
  529.       fp2 = shiftset;
  530.       fp3 = lookaheadset;
  531.       fp4 = lookaheadset + tokensetsize;
  532.  
  533.       while (fp3 < fp4)
  534.     *fp3++ = *fp1++ & *fp2++;
  535.  
  536.       mask = 1;
  537.       fp3 = shiftset;
  538.  
  539.       for (i = 0; i < ntokens; i++)
  540.     {
  541.       if (mask & *fp3)
  542.         fprintf(foutput, "    %-4s\t[reduce  %d  (%s)]\n",
  543.             tags[i], default_rule, tags[rlhs[default_rule]]);
  544.  
  545.       mask <<= 1;
  546.       if (mask == 0)
  547.         {
  548.           mask = 1;
  549.           fp3++;
  550.         }
  551.     }
  552.  
  553.       fprintf(foutput, "    $default\treduce  %d  (%s)\n\n",
  554.           default_rule, tags[rlhs[default_rule]]);
  555.     }
  556.   else if (n - m >= 1)
  557.     {
  558.       cmax = 0;
  559.       default_LA = -1;
  560.       fp4 = lookaheadset + tokensetsize;
  561.  
  562.       if (! nodefault)
  563.     for (i = m; i < n; i++)
  564.       {
  565.         fp1 = LA + i * tokensetsize;
  566.         fp2 = shiftset;
  567.         fp3 = lookaheadset;
  568.   
  569.         while (fp3 < fp4)
  570.           *fp3++ = *fp1++ & ( ~ (*fp2++));
  571.   
  572.         count = 0;
  573.         mask = 1;
  574.         fp3 = lookaheadset;
  575.         for (j = 0; j < ntokens; j++)
  576.           {
  577.         if (mask & *fp3)
  578.           count++;
  579.   
  580.         mask <<= 1;
  581.         if (mask == 0)
  582.           {
  583.             mask = 1;
  584.             fp3++;
  585.           }
  586.           }
  587.   
  588.         if (count > cmax)
  589.           {
  590.         cmax = count;
  591.         default_LA = i;
  592.         default_rule = LAruleno[i];
  593.           }
  594.   
  595.         fp2 = shiftset;
  596.         fp3 = lookaheadset;
  597.   
  598.         while (fp3 < fp4)
  599.           *fp2++ |= *fp3++;
  600.       }
  601.  
  602.       for (i = 0; i < tokensetsize; i++)
  603.         shiftset[i] = 0;
  604.  
  605.       if (shiftp)
  606.         {
  607.           k = shiftp->nshifts;
  608.           for (i = 0; i < k; i++)
  609.         {
  610.           if (! shiftp->shifts[i]) continue;
  611.           symbol = accessing_symbol[shiftp->shifts[i]];
  612.           if (ISVAR(symbol)) break;
  613.           SETBIT(shiftset, symbol);
  614.         }
  615.         }
  616.  
  617.       mask = 1;
  618.       fp1 = LA + m * tokensetsize;
  619.       fp2 = shiftset;
  620.       for (i = 0; i < ntokens; i++)
  621.     {
  622.       int defaulted = 0;
  623.  
  624.       if (mask & *fp2)
  625.         count = 1;
  626.       else
  627.         count = 0;
  628.  
  629.       fp3 = fp1;
  630.       for (j = m; j < n; j++)
  631.         {
  632.           if (mask & *fp3)
  633.         {
  634.           if (count == 0)
  635.             {
  636.               if (j != default_LA)
  637.             {
  638.               rule = LAruleno[j];
  639.               fprintf(foutput, "    %-4s\treduce  %d  (%s)\n",
  640.                   tags[i], rule, tags[rlhs[rule]]);
  641.             }
  642.               else defaulted = 1;
  643.  
  644.               count++;
  645.             }
  646.           else
  647.             {
  648.               if (defaulted)
  649.             {
  650.               rule = LAruleno[default_LA];
  651.               fprintf(foutput, "    %-4s\treduce  %d  (%s)\n",
  652.                   tags[i], rule, tags[rlhs[rule]]);
  653.               defaulted = 0;
  654.             }
  655.               rule = LAruleno[j];
  656.               fprintf(foutput, "    %-4s\t[reduce  %d  (%s)]\n",
  657.                   tags[i], rule, tags[rlhs[rule]]);
  658.             }
  659.         }
  660.  
  661.           fp3 += tokensetsize;
  662.         }
  663.  
  664.       mask <<= 1;
  665.       if (mask == 0)
  666.         {
  667.           mask = 1;
  668.           fp1++;
  669.         }
  670.     }
  671.  
  672.       if (default_LA >= 0)
  673.     {
  674.       fprintf(foutput, "    $default\treduce  %d  (%s)\n",
  675.           default_rule, tags[rlhs[default_rule]]);
  676.     }
  677.  
  678.       putc('\n', foutput);
  679.     }
  680. }
  681.  
  682.  
  683.  
  684. finalize_conflicts()
  685. {
  686.   FREE(conflicts);
  687.   FREE(shiftset);
  688.   FREE(lookaheadset);
  689. }
  690.